//
// Created by cheng on 2021/03/29.
//

#include <iostream>
#include <string>

using namespace std;

int c[100][100];

/**
 * 最长公共子序列
 * @param x 序列x
 * @param y 序列y
 * @return x、y的最长公共子序列
 */
int lcs(string &x, string &y) {
    // 动态规划备忘录
    x = ' ' + x;
    y = ' ' + y;
    // 设置边界
    for (int i = 0; i <= x.size(); i++) {
        c[i][0] = 0;
    }
    for (int i = 0; i <= y.size(); i++) {
        c[0][i] = 0;
    }
    int maxl = 0;
    for (int i = 1; i < x.size(); i++) {
        for (int j = 1; j < y.size(); j++) {
            if (x[i] == y[j]) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
            maxl = max(maxl, c[i][j]);
        }
    }
    return maxl;
}

int main () {
    string x = "abcbdab";
    string y = "bdcaba";
    auto res = lcs(x, y);
    cout << res << endl;
    cout << "  ";
    for (int i = 1; i < y.size(); i++) {
        cout << y[i] << " ";
    }
    cout << endl;
    for (int i = 1; i < x.size(); i++) {
        cout << x[i] << " ";
        for (int j = 1; j < y.size(); j++) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
}